package test2;

public class Solution3_1 {

/**
 //分解到单个元素后再合并
 public static void _mergeSort(int[] arr, int left, int right, int[] temp){
 if (left < right){
 int mid = left + (right - left) / 2;
 //向左递归分解
 _mergeSort(arr, left, mid, temp);
 //向右递归分解
 _mergeSort(arr, mid + 1, right, temp);
 //合并
 _merge(arr, left, mid, right, temp);
 }
 }

 //合并的方法
 /**
 * @param arr 排序的原始数组
 * @param left 左边有序序列的初始索引
 * @param mid 中间索引
 * @param right 右边索引
 * @param temp 中转的数组
 */
/**
 private static void _merge(int[] arr, int left, int mid, int right, int[] temp){
 int i = left; // 初始化i，左边有序序列的初始索引
 int j = mid + 1; // 初始化j，右边有序序列的初始索引
 int t = 0; // 指向temp数组的当前索引
 //1、先把左右两边（有序）的数据按照规则填充到temp数组
 while (i <= mid && j <= right){//有一边完成就跳出循环
 if (arr[i] <= arr[j]){
 temp[t++] = arr[i++];
 } else {
 temp[t++] = arr[j++];
 }
 }
 //2、把剩余数据的一边的数据依次全部填充到temp
 while (i <= mid){
 temp[t++] = arr[i++];
 }
 while (j <= right){
 temp[t++] = arr[j++];
 }
 //3、将temp数组的元素拷贝到arr
 t = 0;
 int tempLeft = left;
 while (tempLeft <= right){
 arr[tempLeft++] = temp[t++];
 }
 }
 */
}
